package lecode;

import java.util.ArrayList;
import java.util.List;

public class 括号生成22 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(2));
    }


    public static List<String> generateParenthesis(int n) {

        List<String> res = new ArrayList<>();
        backtracking(n, res, 0, 0, "");
        return res;
    }

    public static void backtracking(int n, List<String> lists, int left, int right, String tag) {
        //右括号永远不可能大于左括号，大于了就不是有效的
        if (left < right) {
            return;
        }
        //符合要求的
        if (left == right && right == n) {
            lists.add(tag);
            return;
        }
        //加左括号
        if (left < n) {
            backtracking(n, lists, left + 1, right, tag + ('('));
        }
        //加右括号
        if (right < left) {
            backtracking(n, lists, left, right + 1, tag + (')'));
        }
    }
}
